#include <stdlib.h>
#include <string.h>
#include <stdio.h>

#include <common/cache.h> 
#include <common/macro/debug.h> 

/** 
* @brief Create new cache.
* 
* @param maxnodes Maximum number of nodes.
* @param cmp_f Comparator function, used to look up value.
* 
* @return 
*/
API_LIBLOCAL cache_t *cache_new(int maxnodes, generic_cmp_f cmp_f) {
	cache_t *cache;

	cache = malloc(sizeof(cache_t));

	cache->lrulist = linked_list_new();
	cache->data = avltree_new(cmp_f);
	cache->maxnodes = maxnodes;

	cache->removal_f = NULL;
	cache->ctx = NULL;

	return cache;
}

/** 
* @brief Set the callback used when an item is removed from cache.
* 
* @param cache
* @param removal_f
* @param ctx Context for the callback.
*/
API_LIBLOCAL void cache_set_callback(cache_t *cache, cache_removal_f removal_f, void *ctx) {
	assert(cache != NULL);

	cache->removal_f = removal_f;
	cache->ctx = ctx;
}

/** 
* @brief Flush all items in the cache.
* 
* @param cache
*/
API_LIBLOCAL void cache_flush(cache_t *cache) {
	avltree_node_t *node;
	cache_item_t *item;
	linked_list_item_t *lruitem;

	assert(cache != NULL);

	while ((lruitem = linked_list_tail(cache->lrulist)) != NULL) {
		node = lruitem->data;
		item = avltree_node_value(node);

		assert(node != NULL);
		assert(item != NULL);

		if (cache->removal_f != NULL)
			cache->removal_f(avltree_node_key(node), item->data, cache->ctx);
		linked_list_delete(cache->lrulist, item->lruitem);
		avltree_delete(cache->data, node);
		free(item);
	}
}

/** 
* @brief Deallocate memory for the cache. This includes flushing all items.
* 
* @param cache
*/
API_LIBLOCAL void cache_destroy(cache_t *cache) {
	if (cache == NULL) return;

	cache_flush(cache);
	avltree_destroy(cache->data);
	linked_list_destroy(cache->lrulist);
	free(cache);
}

/** 
* @brief Insert a new item into the cache. If the cache would overflow,
* the least recently used (LRU) algorithm is used to pick an item that
* gets removed from the cache.
* 
* @param cache
* @param key
* @param data
* 
* @return Zero for success, -1 otherwise.
*/
API_LIBLOCAL int cache_insert(cache_t *cache, void *key, void *data) {
	avltree_node_t *node;
	cache_item_t *item;
	linked_list_item_t *lruitem;

	assert(cache != NULL);
	/* Data might be NULL. */

	if (avltree_nodes(cache->data) >= cache->maxnodes) {
		/* Least Recently Used discarding */
		lruitem = linked_list_tail(cache->lrulist);

		node = lruitem->data;
		item = avltree_node_value(node);
		if (cache->removal_f != NULL)
			cache->removal_f(avltree_node_key(node), item->data, cache->ctx);
		linked_list_delete(cache->lrulist, item->lruitem);
		avltree_delete(cache->data, node);
		free(item);
	}

	item = malloc(sizeof(*item));
	item->data = data;

	node = avltree_insert(cache->data, key, item);

	/* Node is NULL, if the item is already in the cache. That shouldn't happen. */
	assert(node != NULL);

	/* Crazy magic. Two-way link between the linked list and the AVL tree node. */
	linked_list_insert_before(cache->lrulist, linked_list_head(cache->lrulist), (void*)node);
	((cache_item_t*)node->value)->lruitem = linked_list_head(cache->lrulist);

	return 0;
}

/** 
* @brief Lookup a key in the cache.
* 
* @param cache
* @param key
* @param data Pointer to pointer to the data in cache.
* 
* @return Zero if cache hit, -1 if cache miss.
*/
API_LIBLOCAL int cache_lookup(cache_t *cache, void *key, void **data) {
	avltree_node_t *node;
	cache_item_t *item;

	assert(cache != NULL);
	assert(data != NULL);
	
	node = avltree_search(cache->data, key);
	if (node == NULL)
		return -1; /* Cache miss. */

	item = avltree_node_value(node);

	/* Least Recently Used, move the most recently used to top. */
	linked_list_unlink(cache->lrulist, item->lruitem);
	linked_list_link_before(cache->lrulist, linked_list_head(cache->lrulist), item->lruitem);

	/* We permit touch-like operation. */
	if (data != NULL)
		*data = item->data;

	return 0;
}
